λ¬Έμ
Programmers - 무μ§μ λ¨Ήλ°© λΌμ΄λΈ
π Logic
while (totalTime + ((pq.peek().time - prevTime) * len) <= k) {
int now = pq.poll().time;
totalTime += (now - prevTime) * len;
len -= 1;
prevTime = now;
}
- νμ¬ μμμ λ¨Ήμ μ μλ€λ©΄,
Queueμμ μ μΈνκ³ μ 체 μμ λ¨Ήμ μκ°μ μ¦κ°μν¨λ€. - νμ¬ μμμ λ¨Ήμ μ μλ κ²½μ°κΉμ§ μ΄λ₯Ό λ°λ³΅νκ³ , μ΄ν
totalTimeκ³Ό λ¨μ μμ κ°μlenμ μ΄μ©νμ¬ λ°©μ‘ μ€λ¨ μ΄ν λ¨Ήμ μμμ μ°Ύλλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Food implements Comparable<Food> {
int time;
int idx;
public Food(int time, int idx) {
this.time = time;
this.idx = idx;
}
@Override
public int compareTo(Food f) {
return this.time - f.time;
}
}
class Solution {
public int solution(int[] food_times, long k) {
Queue<Food> pq = new PriorityQueue<>();
// λͺ¨λ μμμ λ¨Ήλλ° κ±Έλ¦¬λ μ΄ μκ°
long foodSum = 0;
int len = food_times.length;
for (int i = 0; i < len; i++) {
pq.add(new Food(food_times[i], i));
foodSum += food_times[i];
}
// μμμ λ€ μμ·¨νλλ° μμ§ Kμ΄κ° λμ§ μμλ€λ©΄ -1 λ°ν
if (foodSum <= k) return -1;
// λ¨Ήλλ° μ¬μ©ν μκ°
long totalTime = 0;
// μ§μ μ λ€ λ¨Ήμ μμ μκ°
long prevTime = 0;
// νμ¬ μμμ λ¨Ήμ μ μλ κ²½μ°, totalTimeμ μ¦κ°
while (totalTime + ((pq.peek().time - prevTime) * len) <= k) {
int now = pq.poll().time;
totalTime += (now - prevTime) * len;
len -= 1;
prevTime = now;
}
ArrayList<Food> remainFoods = new ArrayList<>();
while (!pq.isEmpty()) remainFoods.add(pq.poll());
// idxλ₯Ό κΈ°μ€μΌλ‘ μ€λ¦μ°¨μ μ λ ¬
remainFoods.sort(Comparator.comparingInt(o -> o.idx));
return remainFoods.get((int) ((k - totalTime) % len)).idx + 1;
}
}
βοΈ Review
- μ²μμ
Kμ μμ κ°μλ₯Ό μ΄μ©ν΄ κ° μμμ΄Kμ΄ μ΄ν λ¨μμλ μμ κ³μ°νμ¬ λͺ λ²μ§Έ μμμ λ¨Ήμμ§ κ²°μ νλ λ°©μμ ννλλ°, μλͺ»λ μ κ·Όλ²μ΄μλ€. -
μ°Έκ³ λ₯Ό νλ "μμλμ΄ μ μ κ²μ λ€ λ¨Ήκ² λλ€λ©΄ μ΄μ°¨νΌ κ·Έ λ³΄λ€ μμλμ΄ ν° κ²λ€λ μ΄λ―Έ λ€ λ¨Ήμ μμλ§νΌ λ¨Ήκ² λλ μ "μ μ΄μ©ν μ κ·Όλ²μ μ¬μ©νμλ€.
- μ΄ λ§μ΄ μ μ΄ν΄λμ§ μμ μκ°μ΄ κ±Έλ Έλ€.